#!/usr/bin/env perl
use warnings;
use strict;

#
# subsample k l in_f1 out_f1 ... in_fn out_fn
# uniform-randomly chooses the same k lines from the first l lines of
# each of files in_f1 ... in_fn and writes them to out_f1 ... out_fn.
# No line will be chosen more than once.
# Files are opened with open() so they can be commands, etc., but this means
# that you should annotate your files with < and >, like:
# subsample 5 10 "<xyz.in" ">xyz.out"
#

my $argc = scalar(@ARGV);
$argc > 2 or die "see comments for usage";
my ($k, $l, @f) = @ARGV;
scalar(@f) % 2 == 0 or die "odd number of files given; see comments for usage";

# Must be careful with seeds. If we run this several times in parallel
# we don't necessarily want the same random numbers for each run, as
# we might get if we just used the time. ($$ is the pid.)
srand (time ^ $$ ^ unpack "%L*", `ps axww | gzip -f`);

# fisher_yates_shuffle( \@array ) : generate a random permutation of @array
# in place
# http://www.unix.com.ua/orelly/perl/cookbook/ch04_18.htm
sub fisher_yates_shuffle {
  my $array = shift;
  my $i;
  for ($i = @$array; --$i; ) {
    my $j = int rand ($i+1);
    next if $i == $j;
    @$array[$i,$j] = @$array[$j,$i];
  }
}

# Permute the sample and keep the top k.
# Then sort the top k for easy access, below.
my @sample = 0..($l-1);
fisher_yates_shuffle(\@sample);
@sample = @sample[0..$k-1];
@sample = sort { $a <=> $b } @sample;

while (@f) {
  my $in = shift @f;
  my $out = shift @f;

  open IN, "$in";
  open OUT, "$out";
  my $line = 0;
  my $sample_index = 0;
  while(<IN>) {
    goto done_file if ($sample_index >= @sample);
    if ($sample[$sample_index] == $line) {
      print OUT;
      ++$sample_index;
    }
    ++$line;
  }
  done_file:
  close IN;
  close OUT;
}

# Copyright (c) 2009 John Lees-Miller
# 
# Permission is hereby granted, free of charge, to any person
# obtaining a copy of this software and associated documentation
# files (the "Software"), to deal in the Software without
# restriction, including without limitation the rights to use,
# copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the
# Software is furnished to do so, subject to the following
# conditions:
# 
# The above copyright notice and this permission notice shall be
# included in all copies or substantial portions of the Software.
# 
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
# OTHER DEALINGS IN THE SOFTWARE.

